import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 51. N 皇后
 * https://leetcode-cn.com/problems/n-queens/
 */
class NQueens {
    /**
     * 方法：使用回溯算法解决N皇后问题
     * 
     * Args:
     *   n: int - 棋盘的大小和皇后的数量
     * 
     * Returns:
     *   List<List<String>> - 所有合法的N皇后摆放方案，每个方案是一个字符串列表，表示棋盘的一行
     * 
     * Time: O(N!) - 最坏情况下需要尝试所有可能的皇后摆放位置
     * Space: O(N^2) - 需要存储棋盘状态和递归调用栈
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1]; // 主对角线
        boolean[] diag2 = new boolean[2 * n - 1]; // 副对角线
        backtrack(0, cols, diag1, diag2, board, res);
        return res;
    }

    private void backtrack(int row, boolean[] cols, boolean[] diag1, boolean[] diag2, char[][] board, List<List<String>> res) {
        if (row == board.length) {
            res.add(convertToString(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            int d1 = row - col + board.length - 1; // 映射到 [0, 2n-2]
            int d2 = row + col;
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                board[row][col] = 'Q';
                cols[col] = diag1[d1] = diag2[d2] = true;
                backtrack(row + 1, cols, diag1, diag2, board, res);
                board[row][col] = '.';  // 回溯
                cols[col] = diag1[d1] = diag2[d2] = false;
            }
        }
    }

    private List<String> convertToString(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) list.add(new String(row));
        return list;
    }
}